package oj.oj_155;

/**
 * 155. 最小栈
 * https://leetcode.cn/problems/min-stack/
 */
import java.util.LinkedList;

// 元素类型是 int 类型
public class MinStack1 {
    // 直接用链表存储
    // 压栈是头插
    // 弹栈是头删
    private final LinkedList<Integer> storage = new LinkedList<>();
    private int minValue = Integer.MAX_VALUE;   // 哨兵，记录目前栈里的最小元素
    // 初始值是极大值，保证只要压栈，一定小于这个数

    public MinStack1() {

    }

    public void push(int val) {
        if (val < minValue) {
            minValue = val;
        }
        storage.add(0, val);    // 压栈
    }

    public void pop() {
        if (storage.isEmpty()) {
            return;
        }

        storage.remove(0);      // 这里的 [0] 是下标
    }

    public int top() {
        if (storage.isEmpty()) {
            return -1;
        }

        return storage.get(0);      // [0] 元素就是栈顶元素
    }

    public int getMin() {
        return minValue;
    }

    public static void main(String[] args) {
        MinStack1 stack = new MinStack1();

        stack.push(3);

        stack.push(7);

        stack.push(1);
        // 栈：先进后出；后进先出
        stack.pop();

        stack.pop();

        stack.pop();
    }
}

